'''
https://leetcode.cn/problems/add-binary/?envType=study-plan-v2&envId=top-interview-150
'''

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        m, n = len(a), len(b)
        i, j = m-1, n-1
        carry = 0
        res = []
        while i >= 0 and j >= 0:
            add = int(a[i]) + int(b[j]) + carry
            carry = 1 if add > 1 else 0
            add &= 1
            res.append(str(add))
            i -= 1
            j -= 1
        while i >= 0:
            add = int(a[i]) + carry
            carry = 1 if add > 1 else 0
            add &= 1
            res.append(str(add))
            i -= 1
        while j >= 0:
            add = int(b[j]) + carry
            carry = 1 if add > 1 else 0
            add &= 1
            res.append(str(add))
            j -= 1
        if carry:
            res.append('1')
        return ''.join(reversed(res))

a = '10101'
b = '110000'
print(Solution().addBinary(a, b))